package leetcode.LinkedList;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * @author wangmaolin1
 * @date 2022/1/16 上午11:00
 */
public class _382链表随机节点_中等 {
    /**
     * 给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。
     * <p>
     * 实现 Solution 类：
     * <p>
     * Solution(ListNode head) 使用整数数组初始化对象。 int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。
     * <p>
     * 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/linked-list-random-node 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */

    public static class Solution {
        ListNode head;
        Random random;

        public Solution(ListNode head) {
            this.head = head;
            this.random = new Random();
        }

        /**
         * 蓄水池抽样算法 保证第 i 个节点被抽取到的概率为1/n
         * <p>
         * 空间复杂度：O(1) 时间复杂度：O(N)
         * </p>
         * <p>
         * https://leetcode-cn.com/problems/linked-list-random-node/solution/lian-biao-sui-ji-jie-dian-by-leetcode-so-x6it/
         * </p>
         */
        public int getRandom() {
            ListNode node = head;
            int ans = 0;
            int i = 1;
            while (node != null) {
                if (random.nextInt(i) == 0) {
                    ans = node.val;
                }
                i++;
                node = node.next;
            }
            return ans;
        }
    }

    public static class Solution2 {
        List<Integer> list;
        Random random;


        public Solution2(ListNode head) {
            ListNode node = head;
            list = new ArrayList<>();
            while (node != null) {
                list.add(node.val);
                node = node.next;
            }
            this.random = new Random();
        }

        /**
         * 空间复杂度：O(N)
         * 时间复杂度：O(N)
         */
        public int getRandom() {
            return list.get(random.nextInt(list.size()));
        }
    }
}
